package leetcode.easy;

/**
 * ClassName: $53_MaxSubArray
 * Description:
 * date: 2021-11-04 10:09
 *
 * @author liyifan
 */
public class $53_MaxSubArray {
    public int maxSubArray(int[] nums) {
        int pre = nums[0];
        int res = nums[0];
        for (int i = 1;i < nums.length;i++) {
            pre = Math.max(pre + nums[i], nums[i]);
            res = Math.max(res, pre);
        }
        return res;
    }

    public int maxSubArray2(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int res = 0;
        for(int i = 1;i < n;i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
